import java.util.ArrayList;
import java.util.List;

/**
 * 740. 删除并获得点数
 * https://leetcode-cn.com/problems/delete-and-earn/
 */
public class Solutions_740 {
    public static void main(String[] args) {
        int[] nums1 = {3, 4, 2};  // output: 6
        int[] nums2 = {2, 2, 3, 3, 3, 4};  // output: 9

        List<int[]> inputs = new ArrayList<>();
        inputs.add(nums1);
        inputs.add(nums2);

        for (int[] input : inputs) {
            int result = deleteAndEarn(input);
            System.out.println(result);
        }
    }

    /**
     * 解题思路：动态规划（类似打家劫舍问题）
     * 有 {4, 5, 6}，则存在状态方程：选 5 还是选 4，选 6 + 4 还是选 5 的问题
     */
    public static int deleteAndEarn(int[] nums) {
        // 记录最大值
        int max = nums[0];
        for (int num : nums) {
            max = Math.max(max, num);
        }

        int len = max + 1;
        int[] sum = new int[len];
        for (int num : nums) {
            sum[num] += num;
        }

        int[] dp = new int[len];
        // 初始化 dp 数组
        dp[0] = 0;
        dp[1] = sum[1];

        for (int i = 2; i < len; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + sum[i]);
        }
        return dp[len - 1];
    }
}
